home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 501-525 / disk_504 / roadroute / roadroute.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  30KB  |  868 lines
  1. /* after years of fiddling..
  2.   'v1.0  September 89
  3.   'v1.7  (adds printing, huge files) October 90
  4. 'Jim Butterfield  */
  5.  
  6.    /* compile with lc -Lcd -v <filename> */
  7. #include <proto/exec.h>
  8. #include <proto/dos.h>
  9. #include <stdio.h>
  10. #define BUFFERLINE 50
  11. #define INFOSIZE sizeof(struct FileInfoBlock)
  12. #define TRAILLEN 100
  13.  
  14. /* File Support structures */
  15. struct CityData {
  16.                 char *CityName;              /* full name  w/state */
  17.                 char *StateName;             /* state/province only */
  18.                 struct CityData *CityLink;   /* init letter chain */
  19.                 struct CityData *StateLink;  /* init letter chain */
  20.                 struct RouteData *RoadList;  /* roads to/from city */
  21.                 struct CityData *WorkList;   /* temp job queue */
  22.                 struct CityData *NextCity[2];  /* result links */
  23.       /* Mindist[0] doubles as CityDupe flag during file input */
  24.                 unsigned short MinDist[2];   /* closest so far */
  25.                 unsigned char StateDupe;     /* one name per state */
  26.                 unsigned char Colum;         /* goes with RoadList */
  27.                 };
  28. struct RouteData {
  29.                  struct CityData *CityNum[2];  /* cities each end */
  30.                  unsigned short Dist[2];       /* distance, time */
  31.                  char *Hiway;                  /* name of Highway */
  32.                  struct RouteData *RLink[2];   /* link for each city */
  33.                  unsigned char Colm[2];        /* goes with RLink */
  34.                  };
  35. struct RouteData *Route0, *Route9;
  36. struct CityData *City0, *City9;
  37. struct CityData *CharLink[0x20];
  38. struct CityData *ChStLink[0x20];
  39. static char InBuff[BUFFERLINE];
  40. static struct CityData *Trail[TRAILLEN][2];
  41. unsigned short TrailPoint[2];
  42. void TimeShow(unsigned short,char *);
  43. int CityMatch(struct CityData *,char *);
  44. unsigned short ParseCities(char *,long);
  45. unsigned short ParseRoutes(char *,long);
  46. struct CityData * AskCity();
  47. void Navigate(struct CityData *,struct CityData *);
  48. void main()
  49.   {
  50.   long fh, lok;
  51.   unsigned short Column, ColStart, ColEnd;
  52.   unsigned short NextCol, NewCol;
  53.   unsigned short AllocCount, errnum;
  54.   unsigned short TrackTrail;
  55.   struct FileInfoBlock *fibb;
  56.   long CitySize, RouteSize;
  57.   char *CityBlox, *RouteBlox, *DataScan, *Active;
  58.   char *StringStart, *FieldStart;
  59.   char *CityPoint, *RoutePoint;
  60.   struct CityData *From, *Dest, *Via, *SearchCity;
  61.   struct CityData *FLink;
  62.   struct RouteData *NextRoute, *NewRoute;
  63.   unsigned int Cities, Roads;
  64.   unsigned long CityPSize, RoutePSize;
  65.   unsigned char Ct0;             /* general character work value */
  66.   static unsigned short Result[2][2];
  67.   static unsigned short tTime, tMiles;
  68.   static char ActCity[]="Cities";
  69.   static char ActRoad[]="Roads";
  70.   static char vers[]="$VER: RoadRoute 1.7";
  71.   for (Ct0=0; Ct0 < 0x20; Ct0++) CharLink[Ct0]= 0;
  72.   for (Ct0=0; Ct0 < 0x20; Ct0++) ChStLink[Ct0]= 0;
  73.  
  74.   AllocCount=0;
  75.   errnum=2;                   /* no memory */
  76.   if ( (long) (fibb = (struct FileInfoBlock *) AllocMem(INFOSIZE,0L))
  77.                                                                 != 0L)
  78.     {
  79.     AllocCount=1;
  80.     errnum=3;                   /* file problems */
  81.     fprintf(stderr,"RoadRoute V1.7  ..   Jim Butterfield\n");
  82.     fprintf(stderr,"   Release version:  1990 10 25\n");
  83.     Cities=0;
  84.     Active=ActCity;
  85.     if ( (lok = Lock("Cities",ACCESS_READ)) != 0L)
  86.       {
  87.       if ( (fh=Examine(lok,fibb)) !=0L)
  88.         {
  89.         CitySize=fibb->fib_Size;
  90.         if ( (long) (CityBlox = AllocMem(CitySize,0L)) != 0L)
  91.      {
  92.           AllocCount=2;
  93.           if ( (fh = Open("Cities",MODE_OLDFILE)) != 0L)
  94.             {
  95.             errnum=0;
  96.             Read(fh,CityBlox,CitySize);
  97.             Close(fh);
  98.             }                      /* City file opened   */
  99.      }                        /* data alloc OK */
  100.    }                          /* examine OK    */
  101.         UnLock(lok);
  102.       }                            /* lock OK          */
  103.     }                              /* examine alloc OK */
  104.   if (errnum == 0)
  105.     {
  106.     for (DataScan=CityBlox;DataScan < CityBlox+CitySize;DataScan++)
  107.       if (*DataScan == 0x0A) Cities++;
  108.     CityPSize=Cities*sizeof(struct CityData);
  109.     if ( (long) (CityPoint = AllocMem(CityPSize,0L)) != 0L)
  110.       AllocCount=3;
  111.     else
  112.       errnum=2;
  113.     }
  114.   if (errnum ==0 )
  115.     {
  116.     errnum=3;                   /* file problems */
  117.     Active=ActRoad;
  118.     Roads=0;
  119.     if ( (lok = Lock("Roads",ACCESS_READ)) != 0L)
  120.       {
  121.       if ( (fh=Examine(lok,fibb)) !=0L)
  122.         {
  123.         RouteSize=fibb->fib_Size;
  124.         if ( (long) (RouteBlox = AllocMem(RouteSize,0L)) != 0L)
  125.           {
  126.           AllocCount=4;
  127.           if ( (fh = Open("Roads",MODE_OLDFILE)) != 0L)
  128.             {
  129.             errnum=0;
  130.             Read(fh,RouteBlox,RouteSize);
  131.             Close(fh);
  132.             }                      /* file opened   */
  133.           }                        /* data alloc OK */
  134.         }                          /* examine OK    */
  135.       UnLock(lok);
  136.       }                            /* lock OK          */
  137.     }
  138.   if (errnum == 0)
  139.     {
  140.     for (DataScan=RouteBlox;DataScan < RouteBlox+RouteSize;DataScan++)
  141.       if (*DataScan == 0x0A) Roads++;
  142.     RoutePSize=Roads*sizeof(struct RouteData);
  143.     if ( (long) (RoutePoint = AllocMem(RoutePSize,0L)) != 0L)
  144.       AllocCount=5;
  145.     else
  146.       errnum=2;
  147.     }
  148.   if (errnum == 0)
  149.     {
  150.     Active=ActCity;
  151.     fprintf(stderr,">> %d Cities\n",Cities);
  152.     City0 = (struct CityData *) CityPoint;
  153.     errnum=ParseCities(CityBlox,CitySize);
  154.     }
  155.   if (errnum == 0)
  156.     {
  157.     Active=ActRoad;
  158.     fprintf(stderr,">> %d Roads\n",Roads);
  159.     Route0 = (struct RouteData *) RoutePoint;
  160.     errnum=ParseRoutes(RouteBlox,RouteSize);
  161.     }
  162.   switch (errnum)
  163.     {
  164.     case 0:                /* no errors, do main job */
  165.       Ct0='Y';
  166.       while (Ct0 == 'Y')
  167.         {
  168.         long pFlag; 
  169.         FILE *pHandl;
  170.         TrailPoint[0]=0;
  171.         TrailPoint[1]=0;
  172.         fprintf(stderr,"City from: ");
  173.         if (gets(InBuff) == 0 || *InBuff =='\0')  From=City0;
  174.                       else      From=AskCity();
  175.         fprintf(stderr,"From %s to: ",From->CityName);
  176.         if (gets(InBuff) == 0)
  177.           {
  178.           InBuff[0]='?';
  179.           InBuff[1]='\0';
  180.           }
  181.         Dest=AskCity();
  182.         fprintf(stderr,"%s->%s via (or RETURN):  ",
  183.                                   From->CityName,Dest->CityName);
  184.         Via=0;
  185.         if (gets(InBuff) != 0 && *InBuff != '\0')
  186.           {
  187.           Via = AskCity();
  188.           fprintf(stderr,"\n%s->%s via %s\n",
  189.                  From->CityName,Dest->CityName,Via->CityName);
  190.           Navigate(From,Via);
  191.           Navigate(Via,Dest);
  192.           }
  193.         else
  194.           {
  195.           fprintf(stderr,"\n%s->%s DIRECT\n",From->CityName,Dest->CityName);
  196.           Navigate(From,Dest);
  197.           }
  198.         for (Column=0; Column<2; Column++)
  199.           {
  200.           Result[0][Column]=0;   /* dist */
  201.           Result[1][Column]=0;   /* time */
  202.           SearchCity=From;
  203.           for (TrackTrail=0; TrackTrail <TrailPoint[Column]; TrackTrail++)
  204.             {
  205.             FLink=Trail[TrackTrail][Column];
  206.             NextRoute=SearchCity->RoadList;
  207.             NextCol=SearchCity->Colum;
  208.             while (NextRoute !=0 &&
  209.                    FLink != NextRoute->CityNum[1-NextCol]) 
  210.               {
  211.               NewRoute=NextRoute->RLink[NextCol];
  212.               NewCol=NextRoute->Colm[NextCol];
  213.               NextRoute=NewRoute;
  214.               NextCol=NewCol;
  215.               }
  216.             Result[1][Column]=Result[1][Column]+NextRoute->Dist[1];
  217.             Result[0][Column]=Result[0][Column]+NextRoute->Dist[0];
  218.             SearchCity=FLink;
  219.             }  /* next Link */
  220.           }    /* next Column */
  221.         ColStart=0;
  222.         ColEnd=1;
  223.         if (Result[0][0]==Result[0][1])
  224.           {
  225.           ColStart=1;
  226.           ColEnd=1;
  227.           }
  228.         if (Result[1][0]==Result[1][1])
  229.           {
  230.           ColStart=0;
  231.           ColEnd=0;
  232.           }
  233.         for (Column=ColStart; Column<=ColEnd; Column++)
  234.           {
  235.           fprintf(stderr,"%4d Miles, time: ",Result[0][Column]);
  236.           TimeShow(Result[1][Column],InBuff);
  237.           fprintf(stderr,"%s\n",InBuff);
  238.           } /* next Column */
  239.         if (ColStart != ColEnd)
  240.           fprintf(stderr,"FASTEST, SHORTEST (or BOTH)\n");
  241.         else
  242.           fprintf(stderr,"Press RETURN to continue\n");
  243.         fprintf(stderr," .. or P to print ");
  244.         pHandl=stdout;
  245.         pFlag=0;
  246.         Ct0='B';
  247.         if ((StringStart=gets(InBuff)) != 0) Ct0=*StringStart;
  248.         if (Ct0 > 'Z') Ct0 -=32;
  249.         if (Ct0 =='P')
  250.           {
  251.           pFlag=1;
  252.           Ct0='B';
  253.      pHandl=fopen("prt:","w");
  254.           }     
  255.         if (Ct0 =='S') ColEnd=0;
  256.         if (Ct0 =='F') ColStart=1;
  257.         for (Column=ColStart; Column<=ColEnd; Column++)
  258.           {
  259.           fprintf(pHandl,"From: %s\nTo: %s\n",From->CityName,Dest->CityName);
  260.           if (Via != 0) fprintf (pHandl,"Via: %s\n",Via->CityName);
  261.           tMiles=0;
  262.           tTime=0;
  263.           SearchCity=From;
  264.           for (TrackTrail=0; TrackTrail <TrailPoint[Column]; TrackTrail++)
  265.             {
  266.             FLink=Trail[TrackTrail][Column];
  267.             NextRoute=SearchCity->RoadList;
  268.             NextCol=SearchCity->Colum;
  269.             while (NextRoute > 0 && 
  270.                    FLink!=NextRoute->CityNum[1-NextCol]) 
  271.               {
  272.               NewRoute=NextRoute->RLink[NextCol];
  273.               NewCol=NextRoute->Colm[NextCol];
  274.               NextRoute=NewRoute;
  275.               NextCol=NewCol;
  276.               }   /* wend, no NextRoute */
  277.             tTime=tTime+NextRoute->Dist[1];
  278.             tMiles=tMiles+NextRoute->Dist[0];
  279.             TimeShow(NextRoute->Dist[1],InBuff);
  280.             /*  Print highway link information */
  281.             fprintf(pHandl,"%4d %s ",NextRoute->Dist[0],InBuff);
  282.             StringStart=InBuff;
  283.             FieldStart=SearchCity->CityName;
  284.             while (*FieldStart != ',')
  285.               *StringStart++ =*FieldStart++;
  286.             *StringStart++ =' ';
  287.             *StringStart++ ='-';
  288.             *StringStart++ =' ';
  289.             FieldStart=FLink->CityName;
  290.             while (*FieldStart != ',')
  291.               *StringStart++ =*FieldStart++;
  292.             *StringStart++ =0;
  293.             fprintf(pHandl,"%s via %s\n",InBuff,NextRoute->Hiway);
  294.             SearchCity=FLink;
  295.             }  /* next link */
  296.           fprintf(pHandl,"     Total Miles: %d\n",tMiles);
  297.           TimeShow(tTime,InBuff);
  298.           fprintf(pHandl,"     Driving Time: %s\n",InBuff);
  299.           }  /* next Column */
  300.         if (pFlag==1)
  301.           {
  302.           fprintf(pHandl,"\f");
  303.           fclose(pHandl);
  304.           }
  305.         Ct0='N';
  306.         fprintf (stderr,"Another trip? ");
  307.         if ((StringStart=gets(InBuff)) != 0) Ct0=*StringStart;
  308.         if (Ct0 > 'Z') Ct0 -=32;
  309.         }           /* another trip */
  310.       break;
  311.     case 1:         /* trouble in file data */
  312.       fprintf(stderr,"----> Correct data in file %s and try again.\n",Active);
  313.       break;
  314.     case 2:         /* AllocMem refused */
  315.         fprintf(stderr,"----> Not enough memory to run RoadRoute.\n");
  316.    break;
  317.     case 3:         /* real trouble with file */
  318.         fprintf(stderr,"----> Can't proceed due to unreadable file %s.\n",Active);
  319.         break;
  320.     default:
  321.       fprintf(stderr,"System error: %d\n",errnum);
  322.     }  /* error switch area */
  323.   switch (AllocCount)
  324.     {
  325.     case 5:  FreeMem(RoutePoint,RoutePSize);
  326.     case 4:  FreeMem( (char *) RouteBlox,RouteSize);
  327.     case 3:  FreeMem(CityPoint,CityPSize);
  328.     case 2:  FreeMem( (char *) CityBlox,CitySize);
  329.     case 1:  FreeMem( (char *) fibb,INFOSIZE);
  330.     }  /* memory cleanup */
  331.   if (errnum != 0)
  332.     {
  333.     fprintf(stderr,"Press any key to quit\n");
  334.     gets(InBuff);
  335.     }   
  336.   }
  337.  
  338.  
  339. void TimeShow(Time, Buffer)
  340.   unsigned short Time;
  341.   char *Buffer;
  342.   {
  343.   unsigned short MinFlag, radix, digit, SuppressLimit, FillChar, Hours[2];
  344.   Hours[0]=Time/60;
  345.   Hours[1]=Time%60;
  346.   SuppressLimit=1;
  347.   FillChar=':';
  348.   radix=10000;
  349.   while (radix>Hours[0] && radix>SuppressLimit)
  350.     {
  351.     radix/=10;
  352.     *Buffer++ =' ';
  353.     }
  354.   for (MinFlag=0;MinFlag<2;MinFlag++)
  355.     {
  356.     while (radix>0)
  357.       {
  358.       digit=Hours[MinFlag]/radix;
  359.       Hours[MinFlag]%=radix;
  360.       *Buffer++ =digit+'0';
  361.       radix/=10;
  362.       }  /* more digits */
  363.     *Buffer++ =FillChar;
  364.     FillChar=0;
  365.     SuppressLimit=10;
  366.     radix=10;
  367.     }  /* next MinFlag */
  368.   }
  369.  
  370. int CityMatch(TabPoint,CityText)
  371.   struct CityData *TabPoint;
  372.   char *CityText;
  373.   {
  374.   /* Name must match exactly; state is optional */
  375.   int Match, StateMatch;
  376.   char TablChar, TextChar;
  377.   char *TableName;
  378.   TableName=TabPoint->CityName;
  379.   TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
  380.   TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
  381.   Match=1;
  382.   StateMatch=0;
  383.   while (Match == 1 && TextChar != ',')
  384.     {
  385.     if (TablChar != TextChar)
  386.       {
  387.       if (TablChar ==',' && TextChar =='/') StateMatch=1;
  388.       else Match=0;
  389.       }
  390.     TablChar=*TableName++; if (TablChar > 'Z') TablChar-=0x20;
  391.     TextChar=*CityText++; if (TextChar > 'Z') TextChar-=0x20;
  392.     }
  393.   if (Match==1)
  394.     {
  395.     if (TablChar != 0 && TablChar !=',') Match=0;
  396.     if (TabPoint->MinDist[0]==1 && StateMatch ==0) Match=0;
  397.     }
  398.   return (Match);
  399.   }
  400.  
  401. unsigned short ParseCities(CitiesBlock,CBlockSize)
  402.   char *CitiesBlock;
  403.   long CBlockSize;
  404.   {
  405.   struct CityData *CityStruct, *CityScan;
  406.   char *LineBegin, *EndLine, *NewName, *OldName;
  407.   unsigned short CityError;
  408.   unsigned char CityIndex,NewChar,OldChar;
  409.   unsigned char FoundFlag, StateFlag;
  410.   CityError=0;
  411.   CityStruct = City0;
  412.   LineBegin = CitiesBlock;
  413.   FoundFlag=0;
  414.   for (EndLine=CitiesBlock;EndLine < CitiesBlock+CBlockSize;EndLine++)
  415.   if (*EndLine == ',' || *EndLine == 0x0A)
  416.     {
  417.     if (*EndLine == ',')
  418.       {
  419.       FoundFlag=1;
  420.       CityStruct->CityName=LineBegin;
  421.       /* MinDist[0] used as temporary dupe CityName flag */
  422.       CityStruct->MinDist[0]=0;          /* No City Duplicate Name */
  423.       CityIndex = *LineBegin & 0x1F;        /* strip first char */
  424.       CityScan = CharLink[CityIndex];
  425.       while (CityScan != 0)
  426.         {
  427.         NewName=LineBegin;
  428.         OldName=CityScan->CityName;
  429.         NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  430.         OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  431.         while (NewChar == OldChar && NewChar != ',')
  432.           {
  433.           NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  434.           OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  435.           }
  436.         if (NewChar == OldChar)     /* Dupe City Name */
  437.           {
  438.           CityStruct->MinDist[0]=1;
  439.           CityScan->MinDist[0]=1;
  440.           }
  441.         CityScan = CityScan->CityLink;
  442.         }   /* chain search for input city name */
  443.        CityStruct->CityLink = CharLink[CityIndex];
  444.       CityStruct->RoadList = 0;
  445.       CharLink[CityIndex]=CityStruct;
  446.       LineBegin=EndLine+1;
  447.       }    /* end of comma..City parsing */
  448.     else     /* NewLine */
  449.       {
  450.       *EndLine=0;
  451.       if (FoundFlag ==0)
  452.         {
  453.         fprintf(stderr,"*FILE Cities: NO COMMA:\n%s\n",LineBegin);
  454.         CityError=1;
  455.         }
  456.       FoundFlag=0;
  457.       CityStruct->StateName=LineBegin;
  458.       CityStruct->StateDupe=1;
  459.       CityIndex = *LineBegin & 0x1F;        /* strip first char */
  460.       CityScan = ChStLink[CityIndex];
  461.       StateFlag = 0;
  462.       while (CityScan != 0 && StateFlag == 0)
  463.         {
  464.         NewName=LineBegin;
  465.         OldName=CityScan->StateName;
  466.         NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  467.         OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  468.         while (NewChar == OldChar && NewChar !=0 && OldChar !=0)
  469.           {
  470.           NewChar=*NewName++; if (NewChar > 0x60) NewChar -= 0x20;
  471.           OldChar=*OldName++; if (OldChar > 0x60) OldChar -= 0x20;
  472.           }
  473.         if (NewChar == OldChar)
  474.           {
  475.           CityScan->StateDupe=0;
  476.           StateFlag=1;
  477.           }
  478.         CityScan = CityScan->StateLink;
  479.         }   /* more states in chain */
  480.       CityStruct->StateLink = ChStLink[CityIndex];
  481.       ChStLink[CityIndex]=CityStruct;
  482.       CityStruct++;
  483.       LineBegin=EndLine+1;
  484.       }    /* end of NewLine parsing */
  485.     }
  486.   City9=CityStruct;
  487.   return(CityError);
  488.   }
  489.  
  490. unsigned short ParseRoutes(DataBlock,BlockSize)
  491.   char *DataBlock;
  492.   long BlockSize;
  493.   {
  494.   struct RouteData *RouteStruct;
  495.   struct CityData *CityScan, *FoundCity;
  496.   unsigned short ErrorFlag, CityColm, CityFlag, CityValue, Multiplier;
  497.   unsigned char CtNameKey, Digit;
  498.   char *LineStart,*LineEnd,*FieldStart,*FieldEnd,*NumPtr;
  499.   ErrorFlag=0;
  500.   RouteStruct = Route0;
  501.   LineStart = DataBlock;
  502.   for (LineEnd=DataBlock;LineEnd < DataBlock+BlockSize;LineEnd++)
  503.   if (*LineEnd == 0x0A)
  504.     {
  505.     *LineEnd=0;
  506.     FieldStart=LineStart;
  507.     for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
  508.       {
  509.       for (FieldEnd=FieldStart ;
  510.              *FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
  511.       if (*FieldEnd !=',')
  512.         {
  513.         fprintf(stderr,"*FILE Roads:  MISSING FIELDS:\n%s\n",LineStart);
  514.         ErrorFlag=1;
  515.         }   /* no comma! */
  516.       /* ***** search city name chain */
  517.       CtNameKey = *FieldStart & 0x1F;        /* strip first char */
  518.       CityScan = CharLink[CtNameKey];
  519.       CityValue =0;
  520.       while (CityScan != 0 && CityValue ==0)
  521.         {
  522.         if (CityMatch(CityScan,FieldStart)==1)
  523.           {
  524.           CityValue=1;
  525.           FoundCity=CityScan;
  526.           }
  527.         CityScan = CityScan->CityLink;
  528.         }   /* chain search for input city name */     
  529.       if (CityValue ==0)
  530.         {
  531.         fprintf(stderr,"*FILE Roads:  CITY NOT FOUND:\n%s\n",LineStart);
  532.         ErrorFlag=1;
  533.         }
  534.       RouteStruct->CityNum[CityColm]=FoundCity;
  535.       RouteStruct->RLink[CityColm]=FoundCity->RoadList;
  536.       RouteStruct->Colm[CityColm]=FoundCity->Colum;
  537.       FoundCity->RoadList=RouteStruct;
  538.       FoundCity->Colum=CityColm;
  539.       FieldStart=FieldEnd+1;
  540.       }   /* two-city loop */
  541.     /* Now grab mileage, time, and Hiway */
  542.     for (CityColm=0 ; ErrorFlag==0 && CityColm < 2 ; CityColm++)
  543.       {
  544.       for (FieldEnd=FieldStart ;
  545.                 *FieldEnd !=',' && FieldEnd < LineEnd ; FieldEnd++);
  546.       if (*FieldEnd !=',')
  547.         {
  548.         fprintf(stderr,"FILE Roads:  MISSING FIELDS:\n%s????\n",LineStart);
  549.         ErrorFlag=1;
  550.         }   /* no comma! */
  551.       CityValue=0 ; CityFlag=0;
  552.       Multiplier=10;
  553.       for (NumPtr=FieldStart ; CityFlag==0 && NumPtr < FieldEnd ;
  554.                                                           NumPtr++)
  555.         {
  556.         Digit=*NumPtr;
  557.         if (Digit >='0' && Digit<='9')
  558.           {
  559.           CityValue=CityValue * Multiplier + Digit - '0';
  560.           Multiplier=10;
  561.           }
  562.         else if (Digit ==':') Multiplier = 6;
  563.         }  /* Scan for colon */
  564.       RouteStruct->Dist[CityColm]=CityValue;
  565.       FieldStart=FieldEnd+1;
  566.       }    /* Two value paramemters */
  567.     RouteStruct->Hiway=FieldStart;
  568.     RouteStruct++;
  569.     LineStart=LineEnd+1;
  570.     }    /* end of routefile scan */
  571.   Route9 = RouteStruct;
  572.   return(ErrorFlag);
  573.   }   /* if no error, table build */
  574.  
  575. #define MENUSIZE 15
  576. struct CityData * AskCity()
  577.   {
  578.   char *InputString, *InputName, *TableName;
  579.   unsigned char MulKey, CityKey, InChar, CityChar, StateFlag;
  580.   struct CityData *CityStruct, *CityPStruct;
  581.   unsigned short MenuPointer, MenuList;
  582.   static struct CityData *Menu[MENUSIZE];
  583.  
  584.   InputString=InBuff;
  585.   CityKey = *InputString & 0x1F;        /* strip first char */
  586.   CityStruct = CharLink[CityKey];
  587.   MulKey = 0;              /* Single menu */
  588.   CityPStruct = 0;
  589.   MenuPointer = 0;
  590.   while (CityStruct != 0)
  591.     {
  592.     MenuPointer = 0;
  593.     while ( CityStruct !=0 && MenuPointer < MENUSIZE )
  594.       {
  595.       InputName=InputString;
  596.       TableName=CityStruct->CityName;
  597.       InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  598.       CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  599.       while (InChar == CityChar && InChar != 0)
  600.         {
  601.         InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  602.         CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  603.         }
  604.       if (InChar == 0)
  605.         {
  606.         Menu[MenuPointer++]=CityStruct;
  607.         CityPStruct = CityStruct;
  608.         }
  609.       CityStruct = CityStruct->CityLink;
  610.       }   /* chain search for input city name */
  611.     if ( MenuPointer > 1)
  612.       {
  613.       for (MenuList=0;MenuList < MenuPointer;MenuList++)
  614.         fprintf(stderr,"%d: %s\n",MenuList+1,Menu[MenuList]->CityName);
  615.       fprintf(stderr,">>> Pick 1 to %d:",MenuPointer);
  616.       if (CityStruct != 0)
  617.         {
  618.         fprintf(stderr," or RETURN for more:");
  619.         CityStruct = CityPStruct;
  620.    MulKey=1;           /* Multiple menus */
  621.         }
  622.       else if ( MulKey != 0 )
  623.         {
  624.         fprintf(stderr," or RETURN to restart list:");
  625.         CityStruct = CharLink[CityKey]; /* return to first menu */
  626.         }
  627.       StateFlag=0;
  628.       if ((InputString=gets(InBuff)) != 0)
  629.         {
  630.         InChar=*InputString++;
  631.         while (InChar != 0)
  632.           {
  633.           if (InChar >='0' && InChar<='9')
  634.                   StateFlag=StateFlag * 10 + InChar - '0';
  635.           InChar=*InputString++;
  636.           }
  637.         }     /* endif, not RETURN */
  638.       if (StateFlag < 1 || StateFlag > MenuPointer) StateFlag=1;
  639.         else  CityStruct = 0;
  640.       CityPStruct=Menu[StateFlag-1];      
  641.       }  /* endif cities to pick from */
  642.     }   /* while more cities in list */
  643.   switch (MenuPointer)
  644.     {
  645.     case 0:            /* No city match */
  646.       fprintf(stderr,"Province or State: ");
  647.       if ((InputString=gets(InBuff)) == 0) InputString=City0->CityName;
  648.       /* Search for state as input */
  649.       MenuPointer = 0;
  650.       Menu[MenuPointer]=City0;
  651.       CityKey = *InputString & 0x1F;    /* strip state first char */
  652.       CityStruct = ChStLink[CityKey];
  653.       if (CityStruct == 0) CityStruct = City0;
  654.       while (CityStruct != 0)
  655.         {
  656.         if (CityStruct->StateDupe == 1)   /* one flag set per state*/
  657.           {
  658.           InputName=InputString;
  659.           TableName=CityStruct->StateName;
  660.           InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  661.           CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  662.           while (InChar == CityChar && InChar != 0)
  663.             {
  664.             InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  665.             CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  666.             }
  667.           if (InChar == 0)
  668.             if (MenuPointer < MENUSIZE) Menu[MenuPointer++]=CityStruct;
  669.           }
  670.         CityStruct = CityStruct->StateLink;
  671.         }   /* more states in chain */
  672.       if (MenuPointer == 0)    /* search for first letter state */
  673.         {
  674.         CityStruct = ChStLink[CityKey];
  675.         if (CityStruct == 0) CityStruct = City0;
  676.         while (CityStruct != 0)
  677.           {
  678.           if (CityStruct->StateDupe == 1)
  679.             {
  680.             InputName=InputString;
  681.             TableName=CityStruct->StateName;
  682.             InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  683.             CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  684.             if (InChar == CityChar)
  685.               if (MenuPointer < MENUSIZE) Menu[MenuPointer++]=CityStruct;
  686.             }
  687.           CityStruct = CityStruct->StateLink;
  688.           }   /* while more states in alpha chain */
  689.         }  /* endif, single char state search */
  690.       if (MenuPointer > 1)
  691.         {
  692.         for (MenuList=0;MenuList < MenuPointer;MenuList++)
  693.           fprintf(stderr,"%d: %s\n",MenuList+1,Menu[MenuList]->StateName);
  694.         fprintf(stderr,">>> Pick 1 to %d:",MenuPointer);
  695.         StateFlag=0;
  696.         if ((InputString=gets(InBuff)) != 0)
  697.           {
  698.           InChar=*InputString++;
  699.           while (InChar != 0)
  700.             {
  701.             if (InChar >='0' && InChar<='9')
  702.               StateFlag=StateFlag * 10 + InChar - '0';
  703.             InChar=*InputString++;
  704.             }
  705.           if (StateFlag<1 || StateFlag>MenuPointer) StateFlag=1;
  706.           StateFlag -=1;
  707.           }
  708.         CityStruct=Menu[StateFlag];
  709.         }  /* endif, pick state from list */
  710.       if (MenuPointer == 0) CityStruct=City0;
  711.       if (MenuPointer == 1) CityStruct=Menu[0];
  712.       /* Now track cities within a given state */
  713.       InputString=CityStruct->StateName;
  714.       CityKey = *InputString & 0x1F;        /* strip first char */
  715.         /* Track the state alpha list */
  716.       MulKey=0;             /* not multiple menu */
  717.       CityStruct = ChStLink[CityKey];
  718.       CityPStruct = 0;
  719.       MenuPointer = 0;
  720.       while (CityStruct != 0)  /* search cities in a state */
  721.         {
  722.         MenuPointer = 0;
  723.         while ( CityStruct != 0  && MenuPointer < MENUSIZE )
  724.           {
  725.           InputName=InputString;
  726.           TableName=CityStruct->StateName;
  727.           InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  728.           CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  729.           while (InChar == CityChar && InChar != 0)
  730.             {
  731.             InChar=*InputName++; if (InChar > 0x60) InChar -= 0x20;
  732.             CityChar=*TableName++; if (CityChar > 0x60) CityChar -= 0x20;
  733.             }
  734.           if (InChar == CityChar)
  735.        {
  736.             Menu[MenuPointer++]=CityStruct;
  737.             CityPStruct = CityStruct;
  738.             }
  739.           CityStruct = CityStruct->StateLink;
  740.           }   /* while more cities and space in menu */
  741.         if (MenuPointer > 1)
  742.           {
  743.           for (MenuList=0;MenuList < MenuPointer;MenuList++)
  744.             fprintf(stderr,"%d: %s\n",MenuList+1,Menu[MenuList]->CityName);
  745.           fprintf(stderr,">>> Pick 1 to %d:",MenuPointer);
  746.           if (CityStruct != 0)
  747.             {
  748.             fprintf(stderr," or RETURN for more:");
  749.             MulKey=1;      /* multiple menus */
  750.             CityStruct = CityPStruct;
  751.             }
  752.           else if ( MulKey != 0 )
  753.             {
  754.             fprintf(stderr," or RETURN for to restart list:");
  755.             CityStruct = ChStLink[CityKey]; /* back to first menu */
  756.             }
  757.           StateFlag=0;
  758.           if ((InputName=gets(InBuff)) != 0)
  759.             {
  760.             InChar=*InputName++;
  761.             while (InChar != 0)
  762.               {
  763.               if (InChar >='0' && InChar<='9')
  764.                 StateFlag=StateFlag * 10 + InChar - '0';
  765.               InChar=*InputName++;
  766.               }  /* while more numeric string */
  767.             }  /* endif, non-RETURN */
  768.           }              /* endif, pick city within state */
  769.         if (StateFlag < 1 || StateFlag > MenuPointer) StateFlag =1;
  770.           else  CityStruct = 0;
  771.         CityPStruct=Menu[StateFlag-1];
  772.         }     /* while more cities in state list */
  773.       if (MenuPointer == 0) CityPStruct=City0;
  774.       if (MenuPointer == 1) CityPStruct=Menu[0]; 
  775.       break;
  776.     case 1:             /* unique input city match */
  777.       CityPStruct = Menu[0];
  778.     }    /* endswitch, unique or no match */
  779.   return(CityPStruct);
  780.   }
  781.  
  782. void Navigate(struct CityData *Start,struct CityData *Finish)
  783.   {
  784.   unsigned short Column, Travel;
  785.   unsigned short NextCol, NewCol;
  786.   struct CityData *CityScan;
  787.   struct CityData *BLink, *SearchCity;
  788.   struct CityData *ELink, *FLink, *OtherCity;
  789.   struct RouteData *NextRoute, *NewRoute;
  790.   static unsigned short MiniVal;
  791.   static unsigned short ThisDist[2];
  792.         for (CityScan=City0; CityScan<City9; CityScan++)
  793.           {
  794.           CityScan->WorkList = 0;
  795.           for (Column=0; Column<2; Column++)
  796.             {
  797.             CityScan->MinDist[Column]=9999;
  798.             CityScan->NextCity[Column]=0;
  799.             }
  800.           }
  801.         ELink=Finish;
  802.         MiniVal=0;
  803.         for (Column=0; Column<2; Column++)
  804.           {
  805.           Finish->MinDist[Column]=0;
  806.           ThisDist[Column]=9999;
  807.           }
  808.         SearchCity=Finish;       
  809.         while (SearchCity != 0)
  810.           {
  811.           for (Column=0; Column<2; Column++)
  812.             {
  813.             if (SearchCity->MinDist[Column] < Start->MinDist[Column])
  814.               {
  815.     /*   if (Column==0)
  816.      *   printf("Scanning map at range: %d\n",SearchCity->MinDist[0]); */
  817.             MiniVal=SearchCity->MinDist[Column];
  818.             NextRoute=SearchCity->RoadList;
  819.             NextCol=SearchCity->Colum;
  820.             while (NextRoute != 0)
  821.                 {
  822.                 OtherCity=NextRoute->CityNum[1-NextCol];
  823.                 Travel=MiniVal+NextRoute->Dist[Column];
  824.                 if (OtherCity->MinDist[Column] > Travel)
  825.                   /* found a new shortest path */
  826.                   {
  827.                   OtherCity->MinDist[Column]=Travel;
  828.                   OtherCity->NextCity[Column]=SearchCity;
  829.                   if (OtherCity->WorkList == 0 && ELink!=OtherCity)
  830.                     {
  831.                     BLink=SearchCity;
  832.                     FLink=SearchCity->WorkList;
  833.                     while (FLink!=0 && Travel>FLink->MinDist[Column])
  834.                       {
  835.                       BLink=FLink;
  836.                       FLink=BLink->WorkList;
  837.                       }
  838.                     BLink->WorkList=OtherCity;
  839.                     OtherCity->WorkList=FLink;
  840.                     if (FLink==0) ELink=OtherCity;
  841.                     }  /* build new Worklist */
  842.                   }    /* shorter total distance */
  843.                 if (Travel < ThisDist[Column]) ThisDist[Column]=Travel; 
  844.                 NewRoute=NextRoute->RLink[NextCol];
  845.                 NewCol=NextRoute->Colm[NextCol];
  846.                 NextRoute=NewRoute;
  847.                 NextCol=NewCol;
  848.                 }   /* Try another route from SearchCity */
  849.               }     /* City within target range */
  850.             }       /* Next Column */
  851.           BLink=SearchCity->WorkList;
  852.           SearchCity->WorkList=0;
  853.           SearchCity=BLink;
  854.           }  /* if SearchCity not zero, go back */
  855.         for (Column=0; Column<2; Column++)
  856.           {
  857.           SearchCity=Start;
  858.           FLink=SearchCity->NextCity[Column];
  859.           while (FLink != 0)
  860.             {
  861.             if (TrailPoint[Column]<TRAILLEN)
  862.           Trail[TrailPoint[Column]++][Column]=FLink;
  863.             SearchCity=FLink;
  864.             FLink=SearchCity->NextCity[Column];
  865.             }  /* wend for next FLink */
  866.           }    /* next Column */
  867.   }
  868.